/**
 * @file polygon.cpp
 * @see http://code.google.com/p/mega8-hob/source/browse/trunk/polygon.cpp
 * @author Hamish Cumming & Brian Thorne & Phil Bones
 * @version see SVN revision number
 */

#include "polygon.h"
#include "atto.h"
#include <math.h>

/**
 * Returns the coefficients (a, b, c) for the line which passes through the segment.
 * Assumes that the segment has finite length.
 */
line_t line_from_seg (segment_t segment)
{
    line_t line;
    /* deal with the special cases of vertical & horizontal first */
    if (segment.start.x == segment.end.x)
    { /* vertical */
        line.b = 0;
        line.a = 1;
        line.c = -segment.start.x;
    }
    else if (segment.start.y == segment.end.y)
    { /* horizontal */
        line.a = 0;
        line.b = 1;
        line.c = -segment.start.y;
    }
    else
    { /* general case */
        line.a = (float)(segment.end.y - segment.start.y)
        / (float)(segment.start.x - segment.end.x);
        line.b = 1;
        line.c = -(line.a * segment.start.x + segment.start.y);
    }
    return line;
}

/**
 * Returns true (1) if the point's x and y coordinates lie in the range of the start
 * and end coordinates to within tolerance L_TOL.
 * Should only be used if point is known to lie on the extended line through the segment.
 */
int between (point_t start, point_t end, point_t point)
{
    float maxx, maxy, minx, miny;
    if (start.x > end.x)
    {
        maxx = start.x;
        minx = end.x;
    }
    else
    {
        minx = start.x;
        maxx = end.x;
    }
    if (start.y > end.y)
    {
        maxy = start.y;
        miny = end.y;
    }
    else
    {
        miny = start.y;
        maxy = end.y;
    }
    if ((point.x > minx - L_TOL) && (point.x < maxx + L_TOL
    && point.y > miny - L_TOL) && (point.y < maxy + L_TOL))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

/**
 * Returns the perpendicular distance from the point to the line.
 */
float distance_from_line (line_t line, point_t point)
{
    float dist;
    line_t parallel;
    /* compute the parallel line that passes through point */
    parallel = line;
    parallel.c = -(line.a * point.x + line.b * point.y);
    /* calculate the perpendicular distance between the lines, */
    /* special cases first. */
    if (line.b == 0 || line.a == 0)
    { /* vertical or horizontal */
        dist = fabs (line.c - parallel.c);
    }
    else
    { /* general case */
        float vert = fabs ((line.c - parallel.c) / line.b);
        float horiz = fabs ((line.c - parallel.c) / line.a);
        if (vert * vert + horiz * horiz > L_TOL)
            dist = horiz * vert / sqrt (vert * vert + horiz * horiz);
        else
            dist = 0;
    }
    return dist;
}

/**
 * Returns true (1) if the two line segments intersect.
 * The tolerance L_TOL is employed in tests.
 * If the segments are colinear and overlapping, they are classed as intersecting.
 */
int segments_intersect (segment_t seg1, segment_t seg2)
{
    line_t line1 = line_from_seg (seg1);
    line_t line2 = line_from_seg (seg2);
    /* are the lines parallel? */
    if ((fabs (line1.a - line2.a) < L_TOL2) && (fabs (line1.b - line2.b) < L_TOL2))
    {    /* Yes, so are they colinear? */
        if (fabs (line1.c - line2.c) < L_TOL)
        {
            /* Yes, so are they overlapping? */
            if (between (seg1.start, seg1.end, seg2.start)
            || between (seg1.start, seg1.end, seg2.end)
            || between (seg2.start, seg2.end, seg1.start)
            || between (seg2.start, seg2.end, seg1.end))
                return 1; /* "intersection" found */
        }
        else
        {
            return 0;
        }
    }
    else
    { /* not parallel, so find point of intersection . . . */
        point_t point;
        point.x = (int)((line1.b * line2.c - line2.b * line1.c) / (line1.a * line2.b - line2.a * line1.b));
        point.y = (int)((line1.a * line2.c - line2.a * line1.c) / (line2.a * line1.b - line1.a * line2.b));
        /* . . . and check if the point lies within both segments */
        if (between (seg1.start, seg1.end, point) && between (seg2.start, seg2.end, point))
        {
            return 1; /* "intersection" found */
        }
        else
        {
            return 0;
        }
    }
    return 0;
}

/**
 * Returns true (1) if the point lies within L_TOL of the line segment.
 */
int pnt_on_seg (segment_t segment, point_t point)
{
    line_t line = line_from_seg (segment);
    float dist = distance_from_line (line, point); 
    if (dist < L_TOL)
    { /* I.e. the point lies on the extended line */       
        if (between (segment.start, segment.end, point)){
            return 1; /* point does lie on the segment */}
    }
    return 0; /* point does not lie on the segment */
}

/**
 * Returns true (1) if the point lies within L_TOL of any of the edges of the polygon.
 */
int pnt_on_pgon (linked_list_t* polygon, point_t point)
{
    int on_pgon = 0;
    list_node_t * node = polygon->start_node;
    while (node != NULL && !on_pgon)
    {
        segment_t segment;
        segment.start = *(node->point);
        if (node->next == NULL)
            segment.end = *(polygon->start_node->point);
        else
            segment.end = *(node->next->point);
        if (pnt_on_seg (segment, point))
            on_pgon = 1;
        node = node->next;
    }
    return on_pgon;
}

/**
 * Returns the signed angle in radians subtended by the line segment, with anticlockwise positive.
 * Assumes that the point does not lie on the segment
 */
float seg_angle_subtended (segment_t segment, point_t point)
{
    float thetas = atan2 (segment.start.y - point.y,
    segment.start.x - point.x);
    float thetae = atan2 (segment.end.y - point.y,
    segment.end.x - point.x);
    float angle = thetae - thetas;
    if (angle > PI)
        angle = angle - 2 * PI;
    if (angle < -PI)
        angle = angle + 2 * PI;
    /* the resulting angle is in the range -pi to +pi */
    return angle;
}

/**
 * Returns true (1) if the point lies outside the closed polygon.
 * Assumes that the point does not lie on any of the polygon edges.
 */
int pnt_outside_pgon (linked_list_t* polygon, point_t point)
{
    float angle_sum = 0;
    segment_t segment;
    /* sum the subtended angles for the edges, except for the last */

    list_node_t * node = polygon->start_node->next;
    if (node == NULL)
        return 1;
    while (node != NULL)
    {
        segment.start = *node->previous->point;
        segment.end = *node->point;
        angle_sum = angle_sum + seg_angle_subtended (segment, point);
        node = node->next;
    }
    /* add the subtended angle for the last edge */
    segment.start = *polygon->end_node->point;
    segment.end = *polygon->start_node->point;
    angle_sum = angle_sum + seg_angle_subtended (segment, point);
    return (fabs (angle_sum) < 0.1); /* true if sum is close to zero */
}

/**
 * Returns 1 if the point causes the polygon to intersect itself
 */
int pnt_intersects_pgon(linked_list_t * polygon, point_t point)
{
    /* a shape with less than 3 sides cant intersect itself */
    if (polygon->nodes < 3) 
        return 0;

    segment_t seg1;
    segment_t seg2;
    list_node_t * pnt = polygon->start_node->next;

    seg2.start = *polygon->end_node->point;
    seg2.end = point;

    while (pnt->next != NULL)
    {
        seg1.start = *pnt->previous->point;
        seg1.end = *pnt->point;
        if (segments_intersect(seg1, seg2))
            return 1;
        pnt = pnt->next;
    }
    return 0;

}

/**
 * Return 1 if the polygon can be closed with no intersections 
 * (only the last segment is checked, the others are assumed not to intersect)
 */
int pgon_close(linked_list_t * polygon)
{
	/* a shape with less than 3 sides cant be a polygon */
    if (polygon->nodes < 3) 
        return 0;
    if (polygon->nodes == 3)
        return 1; //a triangle
    
    segment_t seg1;
    segment_t seg2;
    list_node_t * node = polygon->start_node->next->next;//dont need to do first one
    
    seg2.start = *polygon->end_node->point;
    seg2.end = *polygon->start_node->point;
	
	/* do up until the punultimate point */
    while (node->next != NULL)
    {
        seg1.start = *node->previous->point;
        seg1.end = *node->point;
        
        if (segments_intersect(seg1, seg2))
        {
            return 0;
        }
        node = node->next;
    } 
    return 1;
}

/**
 * Return a segment of a polygon that a point is on.
 * If no such segment exists, the segment.start = (-1,-1)
 */
segment_t pnt_on_pgon_segment(linked_list_t * polygon, point_t point)
{
    list_node_t * node = polygon->start_node;
    segment_t segment;
    while (node != NULL)
    {
        segment_t segment;
        segment.start = *(node->point);
        if (node->next == NULL)
            segment.end = *(polygon->start_node->point);
        else
            segment.end = *(node->next->point);
        if (pnt_on_seg (segment, point))
            return segment;
        node = node->next;
    }
    segment.start.x = segment.start.y = -1;
    return segment;
}
